#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class solution
{
public:
    int search(vector<int>& nums, int target)
    {
        // 首先确定是前半部分还是后半部分
        if (target >= nums[0])
        {
            // 前半部分
            if (target == nums[0])
                return 0;
            else
            {
                // target > nums[0] 
                int left = 0, right = nums.size() - 1;
                while (left <= right)// 进行二分查找
                {
                    int mid = left + (right - left) / 2;
                    if (target < nums[mid])
                    {
                        // 代表 target 在mid前面, 且mid属于前一部分
                       right = mid - 1;
                    }
                    else if (target > nums[mid])
                    {
                        // target > nums[mid], 但是这里需要判断mid所处的位置是不是前一部分
                        if (nums[mid] <= nums[nums.size() - 1])
                        {
                            // mid 所处的位置是后一部分
                            right = mid - 1;
                        }
                        else
                        {
                            // mid 所处于的位置是前一部分, 正常处理
                            left = mid + 1;
                        }
                    }
                    else
                    {
                        // 找到目标值
                        return mid;
                    }
                }
                // 这里代表没找到
                return -1;
            }
        }
        else if (target <= nums[nums.size() - 1])
        {
            // 后半部分, 和前半部分相同的处理
            int left = 0, right = nums.size() - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (target > nums[mid])
                {
                    // mid 在后半部分, 正常处理
                    left = mid + 1;
                }
                else if (target < nums[mid])
                {
                    if (nums[mid] >= nums[0])
                    {
                        // mid 在前半部分
                        left = mid + 1;
                    }
                    else
                    {
                        // mid 在后半部分, 正常处理
                        right = mid - 1;
                    }
                }
                else
                {
                    return mid;
                }
            }
            return -1;
        }
        else
            return -1;
    }
    int primary_search(vector<int>& nums, int target)
    {
       // 题意理解错误
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
                return mid;
        }
        return -1;
    }
    int advanced_search(vector<int>& nums, int target)
    {
        // 虽然整体并不有序，但是部分有序
        // 在使用二分查找的思想时，我们可以确定的是
        // mid分割出来的两个部分肯定有一个是有序的
        int size = nums.size();
        if (!size)
        {
            return -1;
        }
        if (1 == size)
        {
            return nums[0] == target ? 0 : -1;
        }
        // 程序运行到这里代表数组个数大于2
        int left = 0, right = size - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;// 找到了
            else// 接下来没有找到, 我们首先找有序的那部分
            {
                // 先假设左边有序
                // if (nums[0] <= nums[mid - 1]) 因为mid - 1有数组越界的问题
                // 所以改一下逻辑
                if (nums[0] <= nums[mid]) // 这里需要等于, 因为等于时也代表mid有序, 原本判断没有等于时, else 的逻辑是 nums[0] >= nums[mid] 
                                          // :这并不能确保右边有序
                {
                    if (nums[0] <= target && nums[mid] > target)
                    {
                        // 代表target肯定在左边的有序部分
                        right = mid - 1;
                    }
                    else 
                    {
                        // target 不在左边有序位置
                        left = mid + 1;
                    }
                }
                else
                {
                    // 右边有序
                    if (target > nums[mid] && target <= nums[size - 1])
                    {
                        // target 肯定在数组左边的有序位置
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }
            }
        }
        return -1;
    }
};
int main()
{

    int num[] = { 4,5,6,7,0,1,2 };
    vector<int> v(num, num + 7);
    int target;
    cin >> target;
    cout << solution().search(v, target) << endl;

    return 0;
}
